from XSY.Graph.Graph import *
from XSY.Base  import *

class StrongComponent:
   '''make a strong component of a given graph.
H.N. Gabow, "Path-based depth-first search for strong and biconnected components", Inforation Processing Letters, V.74,2000, pp107-114
'''
   def __init__(self, G):
      if isinstance(G,Graph):
         self.G=G
         self.S=[]# list is used for stack: push(a)=append(a),and pop(), top=data[-1]
         self.cnt=0; self.scnt=0;
         self.pre= dict() #<_TV, int>();
         self.id= dict() #new Dictionary<_TV, int>(); // id: SN -> SC
         self.path = [] #new Stack<_TV>();
         self.recursiveStack = [] #new Stack<KeyValuePair<_TV, IEnumerator<_TV>>>();

         for v in G.V:
            if v not in self.pre: #vi has not been checked!
               self.scR(v); # make strong_component
      else:
         raise Exception("%s is not Graph!"%type(G))


   def count(self):
      '''return how many strongly connected vertices'''
      return self.scnt


   def isStronglyReachable(self, a, b):
      '''check if a and b are strongly connected'''
      if str(a) == str(b): # the same vertices
         return True
      if a not in self.id:
         raise Exception("%s is invalid vertex!"%a)
      if b not in self.id:
         raise Exception("%s is invalid vertex!"%b)
      return self.id[a] == self.id[b]

   
   def getSCGroup(self, a):
      '''return the strongly connected vertice group containing a'''
      if a in self.id:
         return self.id[a]
      else:
         return -1# no such a group


   def getSC(self, kv):
      ''''''
      for v in self.G.V:
         i = self.getSCGroup(v)
         if i not in kv:
            kv[i]=[] # new kernel vertex
         kv[i].append(v)

 
   def pushRStack(self, w):
      '''push RStack'''
      #print "%s(%s)"%(function_name(),w)
      self.pre[w] = self.cnt; self.cnt += 1
      self.S.append(w); self.path.append(w)
      kv = (w, self.G.outV(w))
      #print "%s",kv[0]
      #for v in kv[1]:
      #   print v
      self.recursiveStack.append(kv)

     
   def scR(self, w):
      '''make the strongly connected components graph'''
      #print "%s(%s)"%(function_name(),w)
      self.pushRStack(w)
      while len(self.recursiveStack)>0:
         kv = self.recursiveStack[-1] # -1 is the last = top index
         pop = True
         for to_v in kv[1]: # kv[1] is G.outV(kv[0])
            if to_v not in self.pre:
               self.pushRStack(to_v)
               pop = False
               break
            elif to_v not in self.id:
               while self.pre[self.path[-1]] > self.pre[to_v]:
                  self.path.pop()
         if pop:
            self.popRStack(kv[0])


   def popRStack(self, w):
      '''pop R Stack'''
      #print "%s(%s)"%(function_name(),w)
      self.recursiveStack.pop()
      if str(self.path[-1]) == str(w):
         self.path.pop()
         v = None
         while True: 
            v = self.S.pop(); self.id[v] = self.scnt
            if (str(v) == str(w)):
               break

         self.scnt += 1
      

   def __str__(self):
      #print 'id=',self.id
      #print 'path=',self.path
      kv = {}
      self.getSC(kv)
      s = ""
      for i in kv:
         s += str(i)+":\n"
         for v in kv[i]:
            s += "\t"+str(v)+"\n"
            
      return s
